import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=332 lang=java
 *
 * [332] 重新安排行程
 */

// @lc code=start
class Solution {
    LinkedList<String> res=new LinkedList<>();
    LinkedList<String> path=new LinkedList<>();
    public List<String> findItinerary(List<List<String>> tickets) {
        Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));//按照目的地进行字典排序即可[出发地，目的地1]和[出发地，目的地2]
        path.add("JFK");
        boolean[] used=new boolean[tickets.size()];
        dfs(tickets,used);
        return res;
    }

    public boolean dfs(List<List<String>> tickets,boolean[] used){
        if(path.size()==tickets.size()+1){
            res=new LinkedList<>(path);
            return true;
        }

        for(int i=0;i<tickets.size();i++){
            if(!used[i]&&tickets.get(i).get(0).equals(path.getLast())){
                path.add(tickets.get(i).get(1));
                used[i]=true;
                if(dfs(tickets, used)){//优化点，只要找到就可以结束了，因为只需要一条有效路径
                    return true;
                };
                used[i]=false;
                path.removeLast();
            }
        }
        return false;
    }
}
// @lc code=end

